This invention relates to pipeline arithmetic units and, more particularly, to a pipeline adder that employs half adders to achieve high throughput.
Some prior art designs of data processing circuits in VLSI still employ the relatively random constructions used in smaller scale integration and in hybrid circuits. Such approaches tend to produce circuits consisting of blocks that perform a particular function well, but the various blocks are different. In spite of the ability to create a large number of transistors within a single VLSI circuit, the temptation is to minimize the number of transistors required for the implementation of each function, so as to maximize the overall functionality of the integrated circuit. Such circuits are difficult to design and test. In addition, such circuits sometimes result in long conducting interconnections which increase stray capacitances and reduce the potential switching speed of the circuit. Perhaps even more importantly, such circuits often have conducting paths of greatly differing lengths and that complicates design of the synchronization circuitry because the varying propagation delays must be accounted for. More recently, VLSI designs have turned more to systematic, modular, designs of the building blocks comprising the integrated circuits but that, per se, does not eliminate design failings that reduce the circuit's maximum operating speed.
Prior art multiplication techniques, for example, have employed the highly modular Carry Save Addition (CSA) technique which comprises rows of adders. In each row of adders an incoming partial product is added to the sum and carry outputs of the previous row. No horizontal connections exist between the adders in each row except for the last row where the carry signal has to propagate horizontally through all the adders cells on that row. Only when this rippling-through has been accomplished is the multiplication product valid.
The overall delay through a multiplier employing CSAs is the ripple-through delay of the last row plus the sum of the delays through one stage in each row. Thus, with a multiplicand of N bits and a multiplier of M bits, the overall delay is approximately M+N times the delay through a single adder cell. Most of the adder cells, by the way, are full adders.
As can be appreciated from the above, ripple through designs carry time penalties because of the need to wait for the rippling-through of carry signals at each stage of the multiplication.
To alleviate these time penalties, "pipelining" has been introduced. In such a design, each cell is a full adder that accepts three bits: a sum bit from the previous row, a partial product bit, and a carry bit from the previous row. Latches are introduced between successive rows, and these latches permit the pipelining of multiplication operations. What that means is that while a partial sum of one multiplication operation is developed in one row based on information stored in latches of the previous row, that previous row may be computing a partial sum of a successive multiplication operation. The technique of placing latches between successive cell rows increases the time between the beginning of the multiplication operation and its completion (latency), but it greatly increases the rate at which successive products appear at the output (throughput).
The problem with prior art pipeline multipliers, however, is that at the last multiplication stage, a carry signal must propagate as described above. That propagation delay becomes the weak link in the circuit's operating speed capability. To overcome the propagation delay in the last adder stage, some artisans have sacrificed simplicity for speed by introducing carry look-ahead adders in the last stage. Look-ahead adders, however, grow in size and complexity with the size of the multiplicand, their implementation does not lend itself to a regular geometric structure, and the delay of even the most efficient look-ahead adder is still greater than the delay of a single adder stage.
It is an object of this invention, therefore, to provide a pipeline adder that avoids ripple-through carry delays and also avoids the pitfalls of look-ahead adders. It is another object of this invention to provide a pipeline adder which may be employed within VLSI designs implementing more complex arithmetic, such as pipeline multipliers.